
/*
1. Node 表示邻接表中的节点
2. Graph 包含邻接表、入度数组和节点总数
3. createGraph 初始化图结构
4. addEdge 添加边并更新入度
5. 拓扑排序:
    使用队列处理入度为0的节点
    逐步减少后继节点的入度，生成拓扑序列
    最后检测结果长度，判断是否存在环

*/
#include <stdio.h>
#include <stdlib.h>

#include "manager.h"

// 创建图并初始化
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjList = (struct Node**)malloc(vertices * sizeof(struct Node*));
    graph->inDegree = (int*)malloc(vertices * sizeof(int));

    // 初始化邻接表和入度
    for (int i = 0; i < vertices; i++) {
        graph->adjList[i] = NULL;
        graph->inDegree[i] = 0;
    }
    return graph;
}

// 添加边（src -> dest，表示dest依赖src）
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src]; // 头插法
    graph->adjList[src] = newNode;
    graph->inDegree[dest]++; // 目标节点入度+1
}

// 拓扑排序函数
int* topologicalSort(struct Graph* graph, int* resultSize) {
    int* order = (int*)malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0; // 队列头尾指针
    int* queue = (int*)malloc(graph->numVertices * sizeof(int));
    int index = 0;

    // 初始队列：入度为0的节点
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // Kahn算法处理
    while (front < rear) {
        int u = queue[front++]; // 取出队首节点
        order[index++] = u;      // 加入拓扑序列

        // 遍历所有邻接节点
        struct Node* temp = graph->adjList[u];
        while (temp != NULL) {
            int v = temp->vertex;
            graph->inDegree[v]--; // 减少入度
            if (graph->inDegree[v] == 0) {
                queue[rear++] = v; // 入队
            }
            temp = temp->next;
        }
    }

    free(queue); // 释放队列内存
    *resultSize = index;

    // 检测是否存在环
    if (index != graph->numVertices) {
        free(order);
        return NULL; // 存在循环依赖
    }
    return order;
}

// 释放图内存
void freeGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct Node* temp = graph->adjList[i];
        while (temp != NULL) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
    }
    free(graph->adjList);
    free(graph->inDegree);
    free(graph);
}

int sort() {
    // 示例：节点索引对应关系 A(0), B(1), C(2), D(3)
    struct Graph* graph = createGraph(4);
    addEdge(graph, 1, 0); // B -> A
    addEdge(graph, 2, 0); // C -> A
    addEdge(graph, 3, 1); // D -> B
    addEdge(graph, 3, 2); // D -> C

    int size;
    int* order = topologicalSort(graph, &size);

    if (order == NULL) {
        printf("存在循环依赖，无法排序！\n");
    } else {
        printf("拓扑排序结果：");
        for (int i = 0; i < size; i++) {
            printf("%c ", order[i] + 'A'); // 转换为字母输出
        }
        free(order);
    }

    freeGraph(graph); // 释放内存
    return 0;
}